#include <iostream>
#include <vector>
using namespace std;
int merge(vector<int>& a, int l, int mid, int r) {
    vector<int> temp(r - l + 1);
    int i = 0;
    int p1 = l;
    int p2 = mid + 1;
    int res = 0;
    while(p1 <= mid && p2 <= r) {
        res += a[p1] < a[p2] ? (r - p2 + 1) * a[p1] : 0; // 大于的后面都是大于的
        temp[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
    }
    while(p1 <= mid) {
        temp[i++] = a[p1++];
    }
    while(p2 <= r) {
        temp[i++] = a[p2++];
    }
    return res;
}
int mergeSort(vector<int>& a, int l, int r) {
    if(l == r) {
        return 0;
    }
    int mid = l + ((r - l) >> 1);
    return mergeSort(a, l, mid) + mergeSort(a, mid + 1, r) + merge(a, l, mid, r);
}

int main() {
    // 问题解释：这个问题是找到各个数左侧比当前位置数小的数的总和
    // 问题可以转换成：各个位置右侧数比当前数大的总和
    vector<int> a = {1, 3, 4, 2, 5};
    cout << "sum : " << mergeSort(a, 0, a.size() - 1);
    return 0;
}